package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 在非负数组（乱序）中找到最小的可分配的id（从1开始编号），数据量1000000
 */
public class T06_最小可用ID_不开额外空间 {
    public static void main(String[] args) {
        int max = 20;
        int[] arr = ArrayUtil.getRandomArrWithoutRepetition(max - 2, 1, max);
        ArrayUtil.print(arr);
        int result = solution(arr, 0, arr.length - 1);
        System.out.println("result = " + result);
        Arrays.sort(arr);
        ArrayUtil.print(arr);
    }

    //解题思路：先找到整个数组中间位置的数，如果中间位置的数是最大值的一半说明左侧是紧密的，可用ID在中位数右侧，否则一定在左侧。
    private static int solution(int[] arr, int p, int r) {
        if (p > r) {
            return p + 1;
        }
        int midIndex = p + (r - p) / 2;//中间下标
        int targetValue = midIndex + 1;//当中间下标左侧无空缺时，中间下标应该对应的值
        int midValue = find(arr, p, r, midIndex - p + 1);//中间位置实际的值(使用查找第k大的元素的方法)
        //实际值和目标值相等，说明左侧紧密，最小可用ID在右侧
        if (midValue == targetValue) {
            return solution(arr, midIndex + 1, r);
        } else {
            //实际值和目标值不相等，说明左侧一定有空缺，最小可用ID在左侧
            return solution(arr, p, midIndex - 1);
        }
    }

    /**
     * 查找第k大的元素
     *
     * @param A
     * @param p
     * @param r
     * @param k
     * @return
     */
    private static int find(int[] A, int p, int r, int k) {
        int q = partition(A, p, r);//获取基准下标
        int kq = q - p + 1;//获取基准是第几大的元素
        if (kq == k) {
            return A[q];
        } else if (kq > k) {
            //基准大于要找的，说明要找的在基准左边，改high
            return find(A, p, q - 1, k);
        } else {
            return find(A, q + 1, r, k - kq);
        }
    }

    private static int partition(int[] A, int p, int r) {
        int pivot = A[p];
        int left = p + 1;
        int right = r;
        while (left <= right) {
            while (left <= right && A[left] <= pivot) {
                left++;
            }
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left < right) {
                ArrayUtil.swap(A, left, right);
            }
        }
        ArrayUtil.swap(A, p, right);
        return right;
    }
}
